Improved Online Square-into-Square Packing

摘要

In this paper, we show an improved bound and new algorithm for the onlinesquare-into-square packing problem. This two-dimensional packing probleminvolves packing an online sequence of squares into a unit square containerwithout any two squares overlapping. The goal is to find the largest area$\alpha$ such that any set of squares with total area $\alpha$ can be packed.We show an algorithm that can pack any set of squares with total area $\alpha\leq 3/8$ into a unit square in an online setting, improving the previous boundof $11/32$.